import java.util.ArrayList;
import java.util.List;
// https://leetcode.cn/problems/restore-ip-addresses/
public class IP {
    class Solution {
        private List<String> res = new ArrayList<>();
        public List<String> restoreIpAddresses(String s) {
            backTracking(new ArrayList<>(),s,0);
            return res;
        }

        private void backTracking(List<String> path , String str , int startIndex)
        {
            if(path.size() == 4 && startIndex == str.length())
            {
                String ip = path.get(0) + "." + path.get(1)+"." + path.get(2)+"." + path.get(3);
                res.add(ip);
                return ;
            }
            for(int i = startIndex ; i < str.length() ; i ++)
            {
                int num = getNum(str,startIndex,i);
                if(num <= 255){
                    //System.out.print(num + " ");
                    path.add(str.substring(startIndex,i + 1));
                    backTracking(path,str,i + 1);
                }else
                {
                    continue;
                }
                path.remove(path.size()-1);
            }
        }
        private int  getNum(String str , int left , int right)
        {
            if(str.charAt(left) == '0' && right != left) return 256;
            if(right - left >= 4) return 256;
            return Integer.parseInt(str.substring(left,right + 1));

        }
    }
}
